package uk.ac.strath.cis.metric_spaces.indices;

import static java.util.Arrays.sort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import uk.ac.strath.cis.metric_spaces.framework.AbstractMetricIndex;
import uk.ac.strath.cis.metric_spaces.framework.Distance;
import uk.ac.strath.cis.metric_spaces.framework.MetricIndex;

/**
 * @author Robert
 *
 * @param <E>
 */
public class VantagePointTree<E> extends AbstractMetricIndex<E> {

    private E root;
    private VantagePointTree<E> left;
    private VantagePointTree<E> right;
    private double median;

    /**
     * @param metric
     */
    public VantagePointTree(Distance<E> metric) {
        super(metric);
    }

    /**
     * @param copy
     */
    public VantagePointTree(VantagePointTree<E> copy) {
        super(copy);
    }

    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.AbstractMetricIndex#insert(java.util.Set)
     */
    public void insert(Set<E> elements) {
        super.insert(elements);
        insert(new ArrayList<E>(elements));
    }

    /**
     * @param elements
     */
    private void insert(List<E> elements) {
        root = elements.get(0);
        if (elements.size() > 1) {
            List<E> subList = elements.subList(1, elements.size());
            Map<E, Double> distances = mapDistancesToPivot(root, subList);
            median = median(distances.values());
            addSubtrees(distances, median);
        }
    }

    private VantagePointTree<E> makeSubtree(List<E> elements) {
        VantagePointTree<E> subtree = null;
        if (elements.size() > 0) {
            subtree = new VantagePointTree<E>(this);
            subtree.insert(elements);
        }
        return subtree;
    }

    private void addSubtrees(Map<E, Double> distances, double median) {
        List<E> leftElements = new ArrayList<E>();
        List<E> rightElements = new ArrayList<E>();

        for (Entry<E, Double> e : distances.entrySet()) {
            if (e.getValue() <= median) {
                leftElements.add(e.getKey());
            } else if (e.getValue() > median) {
                rightElements.add(e.getKey());
            }
        }
        left = makeSubtree(leftElements);
        right = makeSubtree(rightElements);
    }

    private Map<E, Double> mapDistancesToPivot(E pivot, List<E> elements) {
        Map<E, Double> map = new HashMap<E, Double>();
        for (E e : elements) {
            map.put(e, distance(pivot, e));
        }
        return map;
    }

    private static double median(Collection<Double> values) {
        Double[] valuesArray = values.toArray(new Double[values.size()]);
        return median(valuesArray);
    }

    private static double median(Double[] values) {
        int size = values.length;
        if (size < 6) {
            sort(values);
            return values[size / 2];
        } else {
            int n = (size % 5 == 0) ? size / 5 : size / 5 + 1;
            Double[] d = new Double[n];
            for (int i = 0; i < n; i++) {
                int arraySize = (i * 5 + 5 <= size) ? 5 : size - (i * 5);
                Double[] d2 = new Double[arraySize];
                for (int j = 0; j < arraySize; j++) {
                    d2[j] = values[i * 5 + j];
                }
                d[i] = median(d2);
            }
            return median(d);
        }
    }

    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.MetricIndex#rangeQuery(java.lang.Object, double)
     */
    public Set<E> rangeQuery(E element, double radius) {
        return rangeQuery(element, radius, new HashSet<E>());
    }

    private Set<E> rangeQuery(E element, double radius, Set<E> returnSet) {
        double distance = distance(element, root);
        if (distance <= radius) {
            returnSet.add(root);
        }

        if ((left != null) && ((distance - radius) <= median)) {
            left.rangeQuery(element, radius, returnSet);
        }
        if ((right != null) && ((distance + radius) > median)) {
            right.rangeQuery(element, radius, returnSet);
        }

        return returnSet;
    }

    private String toString(StringBuilder sb, VantagePointTree<E> node) {
        if (node == null) {
            return "null";
        }
        sb.append(node.root);
        if ((node.left != null) || (node.right != null)) {
            sb.append("( <=" + node.median);
            toString(sb, node.left);
            sb.append(", >" + node.median);
            toString(sb, node.right);
            sb.append(")");
        }
        return sb.toString();
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        return this.toString(sb, this);
    }
    
    @Override
    public MetricIndex<E> clone() {
    	return new VantagePointTree<E>(this);
    }

}
